package lcof

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/
func buildTree(preorder []int, inorder []int) *TreeNode {
	inMap := make(map[int]int)
	for idx, v := range inorder {
		inMap[v] = idx
	}
	var dfs func(prel, prer, inl, inr int) *TreeNode
	dfs = func(prel, prer, inl, inr int) *TreeNode {
		if prel > prer {
			return nil
		}
		root := &TreeNode{Val: preorder[prel]}
		inRootIndex := inMap[preorder[prel]]
		leftLen := inRootIndex - inl
		root.Left = dfs(prel+1, prel+leftLen, inl, inRootIndex-1)
		root.Right = dfs(prel+leftLen+1, prer, inRootIndex+1, inr)
		return root
	}
	return dfs(0, len(preorder)-1, 0, len(inorder)-1)
}
